package cg.studio.practise;

import java.util.HashMap;
import java.util.HashSet;
import java.util.Map;
import java.util.Set;

import org.junit.Test;

public class Strings
{
  @Test
  public void testMappable()
  {
    String[][] strArrays = new String[][]{ {"foo", "bar"}, {"bar","foo"}, {"foo", "rar"}, {"foo", "ebe"}, {"foo", "bee"} };
    
    for( int i=0; i<strArrays.length; ++i )
    {
      System.out.println( "mappableViaMapAndSet: " + strArrays[i][0] + "=>" + strArrays[i][1] + ": " 
          + mappableViaMapAndSet( strArrays[i][0], strArrays[i][1] ) );
      System.out.println( "mappableVia2Map: " + strArrays[i][0] + "=>" + strArrays[i][1] + ": " 
          + mappableVia2Map( strArrays[i][0], strArrays[i][1] ) );
    }
  }
  
  /**
   * check if str1 can map to str2
   * for example: 
   *   "foo" can't map to "bar", as the f=>b, o=>a, but the second o=>r; so the same o mapped to different chars
   *   "bar" can't map to "foo", as b=>f, a=>o, r=>o; the different chars 'a' and 'r' mapped to same char 'o'
   *   "foo" can't map to "rar"
   *   
   * this method can be implement by map( source=>destination ) and set( destination )
   * or by two maps
   * @param str1
   * @param str2
   * @return
   */
  public static boolean mappableViaMapAndSet( String str1, String str2 )
  {
    if( str1 == null || str2 == null )
      return false;
    if( str1.length() != str2.length() )
      return false;
    
    char[] chars1 = str1.toCharArray();
    char[] chars2 = str2.toCharArray();
    
    //keep the map from source to destination
    Map< Character, Character > map = new HashMap< Character, Character >();
    //keep the destination chars which had been mapped from source. to prevent different source char map to same destination char.
    Set< Character > mappedSet = new HashSet< Character >();
    for( int i=0; i<chars1.length; ++i )
    {
      Character mappedChar = map.get( chars1[i] );
      boolean mapped1 = ( mappedChar != null );
      boolean mapped2 = mappedSet.contains( chars2[i] );
      if( mapped1 != mapped2 )
      {
        return false;
      }
      if( !mapped1 )
      {
        map.put( chars1[i], chars2[i] );
        mappedSet.add( chars2[i] );
      }
      else  //mapped
      {
        if( mappedChar != chars2[i] )
        {
          return false;
        }
      }
    }
    return true;
  }
  
  /**
   * the implementation via 2 maps are more clear,
   * basically, this question is one to one map, means from source a=>b, then, from destination b=>a
   * @param str1
   * @param str2
   * @return
   */
  public static boolean mappableVia2Map( String str1, String str2 )
  {
    if( str1 == null || str2 == null )
      return false;
    if( str1.length() != str2.length() )
      return false;
    
    char[] chars1 = str1.toCharArray();
    char[] chars2 = str2.toCharArray();
    
    //keep the map from source to destination
    Map< Character, Character > sToDMap = new HashMap< Character, Character >();
    Map< Character, Character > dToSMap = new HashMap< Character, Character >();
    for( int i=0; i<chars1.length; ++i )
    {
      //both map should be compatible
      
      Character mappedDest = sToDMap.get( chars1[i] );
      Character mappedSrc = dToSMap.get( chars2[i] );
      if( ( mappedSrc == null && mappedDest != null ) || ( mappedSrc != null && mappedDest == null )  )
        return false;
      if( mappedDest != null && mappedDest != chars2[i] )
        return false;
      if( mappedSrc != null && mappedSrc != chars1[i] )
        return false;
      
      sToDMap.put( chars1[i], chars2[i] );
      dToSMap.put( chars2[i], chars1[i] );
    }
    return true;
  }
}
